package com.stable;

import java.util.*;


/**
 * 
 * @author Taranjeet
 * 
 */
public class OptimalStableMarriage
{
    // Number of men (=number of women)
    private int n ;

    // Preference tables (size nxn)
    private int[][] manPref;
    private int[][] womanPref;

    private static final boolean DEBUGGING = true;
    private Random rand = new Random();

    /**
     * Creates and solves a random stable marriage problem of
     * size n, where n is given on the command line.
     */
    public static void main(String[] args) {
	if (args.length != 1) {
	    System.out.println("Usage: java OptimalStableMarriage n");
	    return;
	}
	int n = Integer.parseInt(args[0]);
	OptimalStableMarriage sm = new OptimalStableMarriage(n);
	//if (n <= 15)
	    sm.printPrefTables();
	    int[] marriage = sm.stable();
	//if (n <= 15)
	    sm.printMarriage(marriage);
	    
	    sm.printPrefTables();
	    
    }

    /**
     * Creates a marriage problem of size n with random preferences.
     */
    public OptimalStableMarriage(int n) {
	this.n = n;
	manPref = new int[n][];
	womanPref = new int[n][];
	for (int i = 0; i < n; i++) {
	    manPref[i] = new int[n];
	    createRandomPrefs(manPref[i]);
	    womanPref[i] = new int[n];
	    createRandomPrefs(womanPref[i]);
	}
    }

    /**
     * Puts the numbers 0 .. v.length - 1 in the vector v
     * in random order.
     */
    private void createRandomPrefs(int[] v) {
	// Create a vector with the values 0, 1, 2, ...
	for (int i = 0; i < v.length; i++)
	    v[i] = i;
	// Create a random permutation of this vector.
	for (int i = v.length - 1; i > 0; i--) {
	    // swap v[i] with a random element v[j], j <= i.
	    int j = rand.nextInt(i+1);
	    int temp = v[i];
	    v[i] = v[j];
	    v[j] = temp;
	}
    }

    /**
     * Returns a stable marriage in the form an int array v,
     * where v[i] is the man married to woman i.
     */
    public int[] stable() {
	// Indicates that woman i is currently engaged to
	// the man v[i].
	int[] current = new int[n];
	final int NOT_ENGAGED = -1;
	for (int i = 0; i < current.length; i++)
	    current[i] = NOT_ENGAGED;

	// List of men that are not currently engaged.
	LinkedList<Integer> freeMen = new LinkedList<Integer>();
	for (int i = 0; i < current.length; i++)
	    freeMen.add(i);
	
	

	// next[i] is the next woman to whom i has not yet proposed.
	int[] next = new int[n];

	//computeRanking();
	while (!freeMen.isEmpty()) {
	    int m = freeMen.remove();
	    int w = manPref[m][next[m]];
	    next[m]++;
	    printDebug("m=" + m + " w=" + w);
	    if (current[w] == NOT_ENGAGED) {
		current[w] = m;
		/*
		 * First Woman shorlist their preference list
		 * which cause Man also remove that woman from their preference list 
		 */
		shortListWomanPref(w,m);
		
	    } 
	    
	    else {
		int m1 = current[w];
		
		if (prefers(w, m, m1)) {
		    current[w] = m;
		    shortListWomanPref(w,m);
		    shotListManPref (m1,w);
		    freeMen.add(m1);
		} else {
			shortListWomanPref(w,m1);
			freeMen.add(m);
		    
		}
	    }	    
	}
	return current;	
    }

    
    
    private void shortListWomanPref(int w, int m) {
    	int uptoPref = -1;
    	for (int i = 0; i < n; i++) {
    		if ((womanPref[w][i] == m)){
    			uptoPref = i;
    		}
    			
		}
    	for (int i = uptoPref + 1; i < n; i++) {
    		
    		if  (!(womanPref[w][i] == -1)){
    		shotListManPref(womanPref[w][i], w);
    		womanPref[w][i] = -1;
    		}
    		
		}
    }

	private void shotListManPref(int m, int w) {
		LinkedList<Integer> women = new LinkedList<Integer>();
		for (int i = 0; i < n; i++) {
			women.addLast(manPref[m][i]);
			
		}
		women.removeFirstOccurrence(w);
		
		for (int i = 0; i < n-1; i++) {
			manPref[m][i] = women.remove();
		}
		manPref[m][n-1] = -1;
		
	}

	/**
     * Returns true iff w prefers x to y.
     */
    private boolean prefers(int w, int x, int y) {
	for (int i = 0; i < n; i++) {
	    int pref = womanPref[w][i];
	    if (pref == x)
		return true;
	    if (pref == y)
		return false;	    
	}
	// This should never happen.
	System.out.println("Error in womanPref list " + w);
	return false;
    }

    public void printPrefTables() {
	System.out.println("manPref:");
	printMatrix(manPref);
	System.out.println("womanPref:");
	printMatrix(womanPref);
    }

    private void printMarriage(int[] m) {
	System.out.println("Married couples (woman + man): ");
	for (int i = 0; i < m.length; i++)
	    System.out.println(i + " + " + m[i]);
    }

    private void printDebug(String s) {
	if (DEBUGGING) {
	    System.out.println(s);
	}
    }

    /**
     * Prints the matrix v.
     */
    private void printMatrix(int[][] v) {
	if (v == null) {
	    System.out.println("<null>");
	    return;
	}
	for (int i = 0; i < v.length; i++) {
	    System.out.print(i + ": ");
		for (int j = 0; j < v[i].length; j++){
			if (v[i][j]==-1) continue;
		System.out.print(v[i][j] + " ");}
	    System.out.println();
	}
    }
}

